package leetcode

/**
 * https://leetcode.cn/problems/regular-expression-matching/
 *
 */
class Solution_10 {
    fun isMatch(s: String, p: String): Boolean {
        if (p.isEmpty()) return  s.isEmpty()
        val first_equal = s.isNotEmpty() && (s.first() == p.first() || p.first() == '.')
        if (p.length >= 2 && p[1] == '*'){
            return isMatch(s,p.substring(2)) || (first_equal && isMatch(s.substring(1),p))
        }
        return first_equal && isMatch(s.substring(1),p.substring(1))
    }
    fun match(s:String,p:String,y:Int,x:Int):Boolean{
        return s[y] == p[x] || p[x] == '.'
    }
    fun isMatch2(s: String, p: String): Boolean {
        val memu = Array(s.length + 1){ BooleanArray(p.length  +1){ false} } //表是前s个字符串和前p个字符是否匹配
        memu[0][0] = true
        for(i in 2..p.length){
            //这里当出现a*b*.*类似这种情况，*可以匹配零个字符，所以也能够匹配上
            memu[0][i] = p[i - 1] == '*' && memu[0][i - 2]
        }
        for(y in 0 until  s.length ){
            for(x in 0 until p.length ){
                if (p[x] == '*'){
                    //求前y个s中的字符是否和前x个p中的字符是否匹配
                    //当*与其前面的字符取值为0个时，就相当于看前y个s中的字符与前x-2个p中的字符串是否匹配
                    //当*与其前面的字符取值为1或者1以上时，就相当于判断前y个s中的字符与前x-1个p中的字符是否匹配
                    memu[y + 1][x + 1] = memu[y + 1][x - 1] || (match(s,p,y,x - 1) && memu[y][x + 1])
                }else{
                    memu[y + 1][x + 1] = memu[y][x] && match(s,p,y,x)
                }
            }
        }
        return memu[s.length][p.length]
    }
}
